// https://leetcode.cn/problems/k-th-symbol-in-grammar/
// Created by ade on 2022/10/20.
//
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    // 接下来的每一行，将前一行中的0替换为01，1替换为10。
    // 0 01 0110 01101001 01101001 10010110
    int kthGrammar(int n, int k) {
        if (n == 1) return 0;
        int ret = kthGrammar(n - 1, (k + 1) / 2);
        if (ret == 1) {
            // 父节点 = 1
            if (k % 2 == 0) return 0;
            else return 1;
        } else {
            // 父节点 = 0
            if (k % 2 == 0) return 1;
            else return 0;
        }
    }
};

int main() {
//    Solution so;
//    cout << so.kthGrammar();
    return 0;
}